package leetcode_day._2023._12;

import java.util.*;

/**
 * 2454.下一个更大元素 IV
 * 算法: 单调栈 + 优先队列
 *
 * @author yezh
 * @date 2023/12/12 14:16
 */
public class _12 {

    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 也可以使用优先队列, 使用栈减少内存消耗和时间, 因为可以确保栈中的元素是单调递减的
        List<Integer> st = new ArrayList<>(n);
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> nums[a]));
        for (int i = 0; i < n; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peek()]) ans[queue.poll()] = nums[i];
            while (!st.isEmpty() && nums[i] > nums[st.get(st.size() - 1)]) {
                queue.offer(st.get(st.size() - 1));
                st.remove(st.size() - 1);
            }
            st.add(i);
        }
        return ans;
    }

}
